/**
 * 经典问题，只能向右或者向下走
 * 问从左上到右下的方案总数
 * 不能走有障碍的格子
 * 注意起点就有障碍的情况
 */
class Solution {

using vi = vector<int>;

vector<vi> D;
int N, M;

public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0] == 1) return 0;

        N = obstacleGrid.size();
        M = obstacleGrid[0].size();
        D.assign(N + 1, vi(M + 1, -1));     

        D[1][1] = 1;
        for(int i=1;i<=N;++i)for(int j=1;j<=M;++j){
            if(1 == i and 1 == j) continue;
            if(1 == obstacleGrid[i - 1][j - 1]){
                D[i][j] = 0;
            }else{
                chkadd(D[i][j], D[i][j - 1]);
                chkadd(D[i][j], D[i - 1][j]);                
            }
        }
        return D[N][M];        
    }

    void chkadd(int & d, int a){
        if(-1 == a) return;
        if(-1 == d) return (void)(d = a);
        return (void)(d += a);
    }
};
